package com.dzu.medium;

import com.dzu.common.ListNode;

/**
 * @author ZhaoDong
 * @date 2023/1/6 10:41
 * @description 61. 旋转链表
 */
public class Test61 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);

        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;

        System.out.println(rotateRight2(l1, 2));

        ListNode l0 = new ListNode(0);
        l0.next = l1;
        l1.next = l2;
        l2.next = null;

        System.out.println(rotateRight2(l0, 4));

    }


    /**
     * 实际上就是将尾结点的next指向头结点，要移动的k位置所在的元素作为尾结点即可
     * @param head
     * @param k
     * @return
     */
    public static ListNode rotateRight2(ListNode head, int k) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode pre = head;

        ListNode last = head;

        int length = 1;
        // 得到链表的长度和最后一个ListNode
        while (last.next != null) {
            length++;
            last = last.next;
        }
        // 得到实际旋转次数
        int loop = k % length;

        int cut = length - loop;

        // 将尾巴接到头上
        last.next = head;

        ListNode resp = null;

        int tempCut = 1;
        // 找到不需要移动的元素最为尾巴，它的下一个元素作为头
        while (pre.next != null) {
            if (tempCut == cut) {
                resp = pre.next;
                pre.next = null;
                break;
            }
            tempCut++;
            pre = pre.next;
        }

        return resp;

    }


    /**
     * 超时
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode rotateRight(ListNode head, int k) {

        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;

        ListNode temp = head;
        for (int i = 0; i < k; i++) {
            while (temp.next != null) {
                pre = temp;
                temp = temp.next;
            }
            pre.next = null;

            temp.next = head;
            head = temp;

        }

        return temp;

    }
}
